package main

import (
	"fmt"
)

/*
执行用时：452 ms, 在所有 Go 提交中击败了52.00%的用户
内存消耗：89.3 MB, 在所有 Go 提交中击败了24.00%的用户
*/
type WordFilter struct {
	preTrie *Trie
	sufTrie *Trie
}

func Constructor(words []string) WordFilter {
	preTrie := NewTrie()
	sufTrie := NewTrie()
	for i, word := range words {
		preTrie.addStr(word, i)
		sufTrie.addStr(reverse(word), i)
	}
	//fmt.Println(preTrie.containsStr("abbba"), preTrie.containsStr("abba"))
	//fmt.Println(sufTrie.containsStr("abbba"), sufTrie.containsStr("abba"))
	return WordFilter{
		preTrie: preTrie,
		sufTrie: sufTrie,
	}
}

func (this *WordFilter) F(pref string, suff string) int {
	idxs1 := this.preTrie.walkTree(pref)
	idxs2 := this.sufTrie.walkTree(reverse(suff))

	return retain(idxs1, idxs2)
}

func reverse(word string) string {
	N := len(word)
	res := make([]byte, N)
	for i, ch := range []byte(word) {
		res[N-1-i] = ch
	}
	return string(res)
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * obj := Constructor(words);
 * param_1 := obj.F(pref,suff);
 */

/*
封装一个前缀树
*/
type Trie struct {
	root *Node
}

type Node struct {
	children []*Node
	isWord   bool
	indexes  *ArrayList //记录以该节点为前缀的所有单词的原index
}

func NewTrie() *Trie {
	return &Trie{&Node{}}
}

func (t *Trie) addStr(str string, index int) {
	chs := []byte(str)
	node := t.root
	for _, ch := range chs {
		if node.children == nil {
			node.children = make([]*Node, 128)
		}
		if node.children[ch] == nil {
			node.children[ch] = &Node{}
			node.children[ch].indexes = NewArrayList()
		}

		node = node.children[ch]
		node.indexes.add(index) //记录此前缀的原index，由于index从小到大添加，indexes是有序的
	}
	node.isWord = true
}

func (t *Trie) containsStr(str string) bool {
	chs := []byte(str)
	node := t.root
	for _, ch := range chs {
		if node.children == nil || node.children[ch] == nil {
			return false
		}
		node = node.children[ch]
	}
	return node.isWord
}

/**
传入前缀pre，遍历Trie中所有符合前缀的单词，并返回这些单词的原下表
*/
func (t *Trie) walkTree(pre string) *ArrayList {
	chs := []byte(pre)
	node := t.root
	for _, ch := range chs {
		if node.children == nil || node.children[ch] == nil {
			return NewArrayList()
		}
		node = node.children[ch]
	}
	//遍历node下面所有分支 dfs会超时
	//resMap := make(map[int]bool)
	//dfs(node, resMap)
	return node.indexes
}

/*
封装一个ArrayList
*/
type ArrayList struct {
	arr []int
	len int
}

func NewArrayList() *ArrayList {
	return &ArrayList{make([]int, 0), 0}
}

func (list *ArrayList) add(e int) {
	list.arr = append(list.arr, e)
	list.len++
}

func (list *ArrayList) get(index int) int {
	return list.arr[index]
}

/**
两个ArrayList都是有序的，取它们交集中最大的元素
*/
func retain(idxs1, idxs2 *ArrayList) int {
	i, j := idxs1.len-1, idxs2.len-1
	for i >= 0 && j >= 0 {
		if idxs1.get(i) > idxs2.get(j) {
			i--
		} else if idxs1.get(i) < idxs2.get(j) {
			j--
		} else {
			return idxs1.get(i)
		}
	}
	return -1
}

func main() {
	//trie := NewTrie()
	//trie.addStr("abc", 0)
	//trie.addStr("ab", 1)
	//trie.addStr("abcd", 2)
	//trie.addStr("bca", 3)
	//fmt.Println(trie.containsStr("abc"))
	//fmt.Println(trie.containsStr("ab"))
	//fmt.Println(trie.containsStr("bc"))
	//
	//l1 := trie.walkTree("a")
	//fmt.Println(l1)

	//map1 := make(map[int]bool)
	//map1[5] = true
	//map1[03] = true
	//map1[4] = true
	//map2 := make(map[int]bool)
	//map2[3] = true
	//map2[0] = true
	//fmt.Println(retain(map1, map2))

	filter := Constructor([]string{"abbba", "abba"})
	res := filter.F("ab", "ba")
	fmt.Println(res)
}
